package algorithm.day01;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @ClassName Demo1
 * @Description TODO
 * @Author 耀酱
 * @Date 2023/6/1 7:54
 * @Version 1.0
 */

public class Demo1 {

    // NO.1 两数之和
    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target
     * 的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     */
    @Test // 方法一： 暴力枚举
    public void get1(){
        int nums[] = new int[]{2,7,11,15};
        int target = 9;
        // target = x + y;  y = target -x
        // 遍历数组，找到target -x 即可
        int count = nums.length;
        for(int i =0;i<count;i++){
            for(int j = i+1;j<count;j++){
                if(nums[j] == target - nums[i]){
                    System.out.println("下标为："+i+" + "+j);
                }
            }
        }
    }
    @Test  // 方法二： 哈希表
    public void get2(){
        // 可以简化找target的复杂度，可以使用哈希表
        Map<Integer,Integer> map = new HashMap<>();
        int nums[] = new int[]{2,7,11,15};
        int target = 9;
        int count = nums.length;
        for(int i=0;i<count;i++){
            // 每次遍历都要检查哈希表
            if(map.containsKey(target-nums[i])){
                // 找到了需要的
                System.out.println("下标为："+i+" + "+map.get(target-nums[i]));
            }
            map.put(nums[i],i); //
        }


    }

    // NO.3 无重复字符的最长子串
    //给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    @Test // map 实现
    public void set1(){
//        这道题主要用到思路是：滑动窗口
//        什么是滑动窗口？
//        其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc
//        满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
//        如何移动？
//        我们只要把队列的左边的元素移出就行了，直到满足题目要求！
//        一直维持这样的队列，找出队列出现最长的长度时候，求出解！
        String s = "abcabcbb";
        if (s.length()==0) // return 0;
            System.out.println("字符串不满足要求");
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;   // 字串最大长度
        int left = 0; // 指向字串起始位置
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){ // 判断map里是否有当前字符
                left = Math.max(left,map.get(s.charAt(i)) + 1); // 当前字符与子串有重复字符，改变字串起始位置left，
            }
            map.put(s.charAt(i),i); // 当前字符与当前字串无重复字符，添加至map
            max = Math.max(max,i-left+1);// 更新最大长度，
        }
        map.entrySet().stream().forEach((entry)->{
            System.out.println("key:"+entry.getKey()+"value:"+entry.getValue());
        });
        System.out.println("最长字串长度为："+max);
    }
    @Test // set集合实现
    public void set2(){
        String s = "abcabcbb";
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        occ.stream().forEach((item) -> {
            System.out.println(item);
        });

        System.out.println("无重复字符子串长度为："+ans);
    }

    // NO. 5 最长回文子串
    //给你一个字符串 s，找到 s 中最长的回文子串。
    //如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。





}
